﻿using DynORM.BLLMapper.Helpers;
using DynORM.ER.Mappers;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DynORM.BLLMapper
{
    public class TopologicalSorter
    {

        public static Dictionary<int, object> TopologicalSort(IEnumerable<object> graph, Func<object, IEnumerable<object>> children)
        {
            List<object> black = new List<object>();
            List<object> gray = new List<object>();
            Stack<object> stack = new Stack<object>();
            int i = 0;
            Dictionary<int, object> graphSorted = new Dictionary<int, object>();

            foreach (object n in graph)
            {
                if (black.Contains(n))
                    continue;
                stack.Push(n);
                gray.Add(n); i++; //enter node
                while (stack.Count != 0)
                {
                    object node = stack.Peek();

                    object next = children(node).Where<object>(poco => !black.Contains(poco)).FirstOrDefault();
                    if (next == null)
                    {
                        stack.Pop();
                        gray.Remove(node); black.Add(node); i++; //leave node
                        graphSorted.Add(i, node);
                    }

                    if (next != null)
                    {
                        if (gray.Contains(next))
                            throw new Exception("Cyclical reference was found.");
                        if (!black.Contains(next))
                        {
                            stack.Push(next);
                            gray.Add(next); i++; //enter node
                        }
                    }
                }
            }
            return graphSorted;
        }

        public static Dictionary<int, object> TopologicalSort(IEnumerable<object> graph, Func<object, IEnumerable<object>, IEnumerable<object>> children)
        {
            List<object> black = new List<object>();
            List<object> gray = new List<object>();
            Stack<object> stack = new Stack<object>();
            int i = 0;
            Dictionary<int, object> graphSorted = new Dictionary<int, object>();

            foreach (object n in graph)
            {
                if (black.Contains(n))
                    continue;
                stack.Push(n);
                gray.Add(n); i++; //enter node
                while (stack.Count != 0)
                {
                    object node = stack.Peek();

                    object next = children(node, graph).Where<object>(poco => !black.Contains(poco)).FirstOrDefault();
                    if (next == null)
                    {
                        stack.Pop();
                        gray.Remove(node); black.Add(node); i++; //leave node
                        graphSorted.Add(i, node);
                    }

                    if (next != null)
                    {
                        if (gray.Contains(next))
                            throw new Exception("Cyclical reference was found.");
                        if (!black.Contains(next))
                        {
                            stack.Push(next);
                            gray.Add(next); i++; //enter node
                        }
                    }
                }
            }
            return graphSorted;
        }

    }
}
